This invention relates generally to communication networks and, more particularly, to techniques for stations or nodes connected to a network to be aware of each others' connection to and departure from the network. Commonly used network layer protocols require neighbors on a communication network to find each other dynamically, to be able to map network layer addresses to data link layer addresses, and to know quickly when a neighbor "dies." The terms "network layer" and "data link layer" can be best understood from a brief background description of computer networks in general.
A computer network is a collection of autonomous computers connected together to permit sharing of hardware and software resources, and to increase overall reliability. The term "local area network" (LAN) is usually applied to computer networks in which the computers are located in a single building or in nearby buildings, such as on a college campus or at a single corporate site. A bridge is a device that is connected to at least two LANs and serves to pass message frames or packets between LANs, such that a source station on one LAN can transmit data to a destination station on another LAN, without concern for the location of the destination. Bridges are useful and necessary network components, principally because the total number of stations on a single LAN is limited. Bridges can be implemented to operate at a selected layer of protocol of the network. A detailed knowledge of network architecture is not needed for an understanding of this invention, but a brief description follows by way of further background.
A widely accepted model for network architectures is known as the International Standards Organization (ISO) Open Systems Interconnection (OSI) reference model. The OSI reference model is not itself a network architecture, but rather it specifies a hierarchy of protocol layers and defines the function of each layer in the network. Each layer in one computer connected to the network communicates with the corresponding layer in another computer connected to the network, in accordance with a protocol defining the rules of this communication. In reality, information is transferred down from layer to layer in one computer, then through a channel medium and back up the successive layers of the other computer. However, for purposes of design of the various layers and understanding their functions, it is easier to consider each of the layers as communicating with its counterpart at the same level, in a "horizontal" direction.
The lowest layer defined by the OSI model is called the physical layer, and is concerned with transmitting raw data bits over the communication channel. Design of the physical layer involves issues of electrical, mechanical or optical engineering, depending on the medium used for the communication channel. The layer next to the physical layer is called the data link layer. The main task of the data link layer is to transform the physical layer, which interfaces directly with the channel medium, into a communication link that appears error-free to the next layer above, known as the network layer. The data link layer performs such functions as structuring data into packets or frames, and attaching control information to the packets or frames, such as checksums for error detection, and packet numbers.
The functions of finding neighboring nodes and mapping network layer addresses to data link layer addresses are relatively simple to implement in many conventional local area networks, and involve "multicasting" of messages on the LAN. A multicast message is one that is transmitted simultaneously to multiple destination nodes. If each active node sends a multicast message advertising its presence on the network, all of the other nodes are immediately aware of all of the active nodes on the network. Unfortunately, this simple approach is not available when the nodes are connected to certain types of telecommunications systems, such as SMDS (Switched Megabit Data Service) or X.25, since these media do not support the multicast capability in an efficient manner.
An obvious solution to this problem would be for each node to announce its presence on the network by sending a "Hello" message to every other node. But this is highly inefficient and costly because it requires a number of messages roughly proportional to N.sup.2, where N is the number of nodes. This overhead is most significant in a system in which each message transmitted incurs an incremental cost. Another solution would be to manually configure each of the nodes, such that each node starts operation with a preprogrammed knowledge of the identities of all of the other nodes. For relatively large systems, manual configuration is impractical. Any change in configuration, even if adding or deleting only one new node, requires reconfiguration of all of the remaining nodes.
Accordingly, there is a need for a new technique for automatically generating and updating a list of active nodes and distributing it to the nodes. Preferably, the new approach should be less costly in terms of the communication channel bandwidth it uses to accomplish this goal. The present invention meets this need.